package year2023.recursion;

import java.util.HashSet;
import java.util.Set;

/*
括号组合
请设计一种算法,打印n对括号的全部有效组合(即左右括号正确配对).

输入:3

输出:()()(),(()()),()(()),(())(),((()))
 */

public class Code04_BracketCombination {

    public static void main(String[] args) {
        Code04_BracketCombination obj = new Code04_BracketCombination();
        //HashSet 好处去重
        Set<String> test = obj.parenthesis(3);
        Set<String> test1 = obj.parenthesis1(3);
        System.out.println(test);
        System.out.println(test1);
    }


    //recursion
    public Set<String> parenthesis(int n){
        Set<String> s_n = new HashSet<>();
        if (n == 1){
            s_n.add("()");
            return s_n;
        }
        // s_n-1
        Set<String> s_n_1 = parenthesis(n - 1);
        for (String eOfN_1 : s_n_1) {
            s_n.add("()" + eOfN_1);
            s_n.add(eOfN_1 + "()");
            s_n.add("(" + eOfN_1 + ")");
        }
        return s_n;
    }

    //iteration
    public Set<String> parenthesis1(int n){
        Set<String> res = new HashSet<>();
        res.add("()");
        if (n == 1) return res;
        for (int i = 2; i <= n; i++) {
            Set<String> res_new = new HashSet<>();
            for (String e : res) {
                res_new.add("()" + e);
                res_new.add(e + "()");
                res_new.add("(" + e + ")");
            }
            res = res_new;
        }
        return res;
    }

}
